package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

/**
 * @ClassName Medium_79_WordSearch
 * @Description Medium_79_WordSearch
 * @Author wanghaiwei
 * @Date 2023/3/23 13:52
 */
public class Medium_79_WordSearch {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) {
            return false;
        }
        if (board[0] == null || board[0].length == 0) {
            return false;
        }
        if (word == null || word.length() == 0) {
            return false;
        }
        for (int charRowIdx = 0; charRowIdx < board.length; charRowIdx++) {
            for (int charColIdx = 0; charColIdx < board[0].length; charColIdx++) {
                //先找到"线头"，顺着线头往下找，如果线头不对，就不要开始查找
                if (board[charRowIdx][charColIdx] != word.charAt(0)) {
                    continue;
                }
                int[][] searchedIdxs = new int[board.length][board[0].length];
                if (backtrack(board, word, 0, charRowIdx, charColIdx, searchedIdxs)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(char[][] board, String word, int wordIdx, int charRowIdx, int charColIdx, int[][] searchedIdxs) {
        if (searchedIdxs[charRowIdx][charColIdx] == 1) {
            return false;
        }
        if (board[charRowIdx][charColIdx] != word.charAt(wordIdx)) {
            return false;
        }
        //字符匹配并且搜索的字符串已经到达结尾
        if (wordIdx == word.length() - 1) {
            return true;
        }
        //标记当前位置已经成功被搜索
        searchedIdxs[charRowIdx][charColIdx] = 1;
        if ((charRowIdx - 1) >= 0 && backtrack(board, word, wordIdx + 1, charRowIdx - 1, charColIdx, searchedIdxs)) {
            return true;
        }
        if ((charRowIdx + 1) < board.length && backtrack(board, word, wordIdx + 1, charRowIdx + 1, charColIdx, searchedIdxs)) {
            return true;
        }
        if ((charColIdx - 1) >= 0 && backtrack(board, word, wordIdx + 1, charRowIdx, charColIdx - 1, searchedIdxs)) {
            return true;
        }
        if ((charColIdx + 1) < board[0].length && backtrack(board, word, wordIdx + 1, charRowIdx, charColIdx + 1, searchedIdxs)) {
            return true;
        }
        searchedIdxs[charRowIdx][charColIdx] = 0;
        return false;
    }

    public static void main(String[] args) {
        Medium_79_WordSearch solution = new Medium_79_WordSearch();
        boolean result = solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED");
        Assert.isTrue(result, "Input: board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCCED\" 计算错误，预期true，实际false");
        result = solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "SEE");
        Assert.isTrue(result, "Input: board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word =\"SEE\" 计算错误，预期true，实际false");
        result = solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCB");
        Assert.isTrue(!result, "Input: board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word =\"ABCB\" 计算错误，预期false，实际true");
        result = solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCESEEEFS");
        Assert.isTrue(result, "Input: board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"E\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word =\"ABCESEEEFS\" 计算错误，预期true，实际false");
    }
}
